#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#include "array.h"

Array* create_arr(size_t len)
{
    //给数据结构分配内存
    Array* arr = malloc(sizeof(Array));
    //给元素分配内存
    arr->base = malloc(len);
    //初始化元素长度和元素数量
    arr->len = len;
    arr->cnt = 0;
    return arr;
}

void destory_arr(Array* arr)
{
    //释放存储元素的内存空间
    free(arr->base);
    //释放数据结构的内存
    free(arr);
}

bool add_arr(Array* arr, void* val)
{
    //检查结构体书否已满
    if (arr->cnt >= arr->len)
        return false;
    arr->base[arr->cnt++] = val;
    return true;
}

bool insert_arr(Array* arr, size_t index, void* val)
{
    if (arr->cnt >= arr->len)
        return false;
    if (index > arr->cnt)
        return false;
    if (index == arr->cnt)
    {
        add_arr(arr, val);
        return true;
    }
    //int tmp = arr->cnt;
    //把index后的元素向前移动1位，空位插入新数据
    //while(tmp-- > index) arr->base[tmp+1] = arr->base[tmp];
    memmove(arr->base + index + 1, arr->base + index,(arr->cnt - index));
    //arr->base[index] = val;
    memmove(arr->base + index, &val, 1);
    arr->cnt++;
    return true;
}

bool del_index_arr(Array* arr, size_t index)
{
    //检查下标是否合法
    if (arr->cnt <= index)
        return false;
    //把index后的元素向前移动1位，覆盖原来数据
    //while(index++ < arr->cnt) arr->base[index-1] = arr->base[index];
    memmove(arr->base + index, arr->base + index + 1,arr->cnt - index - 1);
    arr->cnt--;
    return true;
}

bool del_val_arr(Array* arr, void* val,CMP cmp)
{
    for (int i = 0; i < arr->cnt; i++)
    {
        //找到val所在的位置，并按位置删除
        if (0 == cmp(arr->base[i],val))
        {
            return del_index_arr(arr, i);
        }
    }
    return false;
}

bool mod_index_arr(Array* arr, size_t index, void* val)
{
    //检查index合法性
    if (index >= arr->cnt)
        return false;
    arr->base[index] = val;
    return true;
}

bool mod_val_arr(Array* arr, void* old_data, void* new_data,CMP cmp)
{
    for (int i = 0; i < arr->cnt; i++)
    {
        if (0 == cmp(arr->base[i],old_data))
        {
            return mod_index_arr(arr, i, new_data);
        }
    }
    return false;
}
//顺序查找
int query_arr_order(Array* arr, void* key,CMP cmp)
{
    for (int i = 0; i < arr->cnt; i++)
    {
        if (0 == cmp(arr->base[i], key))
        {
            return i;
        }
    }
    return -1;
}
//二分查找
int query_arr_binary(Array* arr, void* key,CMP cmp)
{
    int min = 0, max = arr->cnt - 1;
    while (min <= max)
    {
        int p = (min + max) / 2;
        int b = cmp(arr->base[p], key);
        if (b > 0)
        {
            max = p - 1;
        }
        else if (b < 0)
        {
            min = p + 1;
        }
        else
        {
            return p;
        }
    }
    return -1;
}
//调整参数从而适合递归调用
int _query_arr_binary_re(Array* arr, int min, int max, void* key,CMP cmp)
{
    //先设计出口 是否到达边界
    if (min > max)
        return -1;
    //计算中间位置
    int p = (min + max) / 2;
    //比较
    int b = cmp(arr->base[p], key);
    //大于0表示key小于p位置的值，所以在左边，max变成中间值-1，反之min改变
    //如果是0则表示相等找到了
    if (b > 0)
    {
        return _query_arr_binary_re(arr, min, p - 1, key,cmp);
    }
    else if (b < 0)
    {
        return _query_arr_binary_re(arr, p + 1, max, key,cmp);
    }
    else
    {
        return p;
    }
}
//
int query_arr_binary_re(Array* arr, void* key,CMP cmp)
{
    return _query_arr_binary_re(arr, 0, arr->cnt - 1, key,cmp);
}

void sort_arr(Array* arr,CMP cmp)
{
    //冒泡排序对数据有序性敏感
    //flag表示当前是否有序，如果已经有序则不排列
    //如果flag在一轮比较后还是false，说明已经有序，不需要排列
    //如果发生了交换则说明不一定有序
    bool flag = true;
    for (int i = arr->cnt - 1; i > 0 && flag; i--)
    {
        flag = false;
        for (int j = 0; j < i; j++)
        {
            if (arr->base[j] > arr->base[j + 1])
            {
                swap(arr->base[j + 1], arr->base[j]);
                //有发生交换说明需要继续排序
                flag = true;
            }
        }
    }
}
//遍历
void traversal_arr(Array* arr,FUNC func)
{
    for (int i = 0; i < arr->cnt; i++)
    {
        func(arr->base[i]);
    }
}
//根据下标访问元素
void* get_index_arr(Array* arr, int index)
{
    return arr->base[index];
}
